package com.dataStructure.Map.hashMap;

public class MyHashMap<K,V> {

	private Entry<K,V>[] entries;
	static final int DEFAULT_INITIAL_CAPACITY = 16;//默认数组长度
	private int size;
	
	public MyHashMap(){
		entries = new Entry[DEFAULT_INITIAL_CAPACITY];
		size = DEFAULT_INITIAL_CAPACITY;
	}	
	
	public int getSize(){
		return size;
	}
	
	int indexFor(int h, int length){
		return h % (length -1);
		
	}
	
	public V get(K key){
		if (key == null) 
			return null;
		int hash = key.hashCode(); // the hash value of key
		//find the location of array
		int index = indexFor(hash, entries.length);
		
		//locate the position of array , and then iterate the linklist to find the value
		for (Entry<K, V> e = entries[index]; e != null; e = e.next) {
			K k = e.getKey();
			if (key.hashCode() == hash && (key == k || key.equals(k) )) {
				return e.getValue();
			}
		}
		
		return null;
	}
	
	/**
	 * 如果hashmap已经存在key，则用新的value覆盖原来的value，并返回oldValue，否则返回null
	 * @param key
	 * @param value
	 * @return
	 */
	public V put(K key,V value){
		if (key == null) 
			return null;
		int hash = key.hashCode(); // the hash value of key
		//find the location of array
		int index = indexFor(hash, entries.length);
		
		//check if the key is already exist in this map
		for (Entry<K, V> e = entries[index]; e != null; e = e.next) {
			Object k = e.getKey();
			if (k.hashCode() == hash && (k == key || key.equals(k))) {
				V oldValue = e.value;
				e.value = value;
				return oldValue;
			}
		}
		
		//reach here means key dose not exist, need to create a new one
		//good strategy! make data-insert quick
		Entry<K, V> e = entries[index];
		entries[index] = new Entry<K, V>(key,value,e);
		return null;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyHashMap<Integer, Integer> map = new MyHashMap<Integer, Integer>();
        map.put(1, 90);
        map.put(2, 95);
        map.put(17, 85);
    
        System.out.println(map.get(1));
        System.out.println(map.get(2));
        System.out.println(map.get(17));
        System.out.println(map.get(null));
	}

}
